/*
题目: 连通网络的操作次数
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

https://leetcode.cn/problems/number-of-operations-to-make-network-connected/description/
 */
public class MakeConnected {
    int[] uf = null;
    public int makeConnected(int n, int[][] connections) {
        // 最小生成树 ?
        // 有 n 个电脑, 则至少存在 n - 1 条边
        if (connections.length < n - 1) return -1;

        // result = 连通块的数量 - 1
        // 每成功进行一次合并, 连通块的数量就会 -1
        uf = new int[n];
        Arrays.fill(uf, -1);

        for (int[] cur : connections) {
            unit(cur[0], cur[1]);
        }

        return collectionsNum() - 1;
    }

    private boolean unit(int x, int y) { // 返回一个值, 表示是否合并成功
        int xRoot = root(x), yRoot = root(y);
        if (xRoot == yRoot) return false;

        uf[xRoot] += uf[yRoot];
        uf[yRoot] = xRoot;
        return true;
    }

    private int root(int x) {
        // uf[x] >= 0 说明还有父亲, 小于 0 了就说明是顶点了, 返回这个下标
        return uf[x] >= 0 ? root(uf[x]) : x;
    }


    private int collectionsNum() { // 获取连通块数量, 即集合数量
        int count = 0;
        for (int u : uf) {
            if (u < 0)  count ++;
        }
        return count;
    }
}
